//Name: Stephen Durfey
//Prof: Dr. Poor
//Date: November 17, 2008

#include <iostream>
#include <sstream>
using namespace std;

class Heap{

public:

	//Build empty heap
	Heap();

	//Builds a heap from list
	Heap(int list[], int listSize);

	//not used for this lab
	void insert(int x);

	//removes the smallest element in the heap
	int remove();

	//returns the size of the heap;
	int size();

private:

	//heap is implemented as an array of 25 ints
	//better implementation would be a dynamic array
	int heap[25];

	//number of elements currently in the heap
	int heapSize;

	//down heap function
	void heapify(int location);

	//up heap function for insert
	void upheaval(int location);

	//build heap function used by constructor that takes in array
	void buildHeap();

	int leftChild(int index);
	int rightChild(int index);
	int parent(int index);

};


Heap::Heap()
{
	heapSize = 0;
}

Heap::Heap(int list[], int listSize)
{

	//remember heaps start at 1 not zero
	heap[0]=-1;

	for(int i=0; i < listSize; i++)
	{
		heap[i+1] = list[i];
	}

	heapSize = listSize;

	buildHeap();

}
void Heap::insert(int x)
{
	//location to insert is heapSize+1
	//(Recall, 0th location not used)
	heap[heapSize+1] = x;
	heapSize++;
	//heapsize points to index of last element now
	//reheap
	upheaval(heapSize);

}

int Heap::remove()
{
//	int left = leftChild(0) + 1;
//	int right = rightChild(0) + 1;
//	if(!(heapSize == 0))
//	{
//		if(heap[left] < heap[right])
//		{
//			int temp = heap[left];
//			heapify(1);
//			return temp;
//		}
//		else
//		{
//			int temp = heap[right];
//			heapify(2);
//			return temp;
//		}
	if(!(heapSize == 0))
	{
		int temp = heap[1];
		heap[1] = heap[heapSize--];
		heapify(1);
		return temp;
	}
	//}
}

int Heap::size()
{
	return heapSize;
}



void Heap::heapify(int location)
{
	int left, right, smallest;
	left = leftChild(location);
	right = rightChild(location);

	if(left <= (heapSize))
	{
		if(left == (heapSize)) //if child is last node in heap
			smallest = left;
		else
		{
			if(heap[left] < heap[right])
				smallest = left;
			else
				smallest = right;
		}
		if(heap[smallest] < heap[location]) //if smallest child is less than parent
		{
			int temp = heap[location];
			heap[location] = heap[smallest];
			heap[smallest] = temp;
			heapify(smallest);
		}
	}
}

void Heap::upheaval(int location)
{
	//coming soon as it gives away the answer to heapify
}

void Heap::buildHeap()
{
	for(int index = (heapSize / 2); index > 0; index--)
	{
		heapify(index);
	}
}

int Heap::leftChild(int index)
{
	return index*2;
}
int Heap::rightChild(int index)
{
	return index*2+1;

}
int Heap::parent(int index)
{
	return index/2;
}

//not part of the heap class. but uses a heap
void heapSort(int list[], int size)
{

	int* temp;
	temp = new int[size];

	Heap h(list,size);
	for(int i=0; i < size; i++)
	{
		temp[i] = h.remove();
	}

	for(int j=0; j < size; j++)
	{
		list[j] = temp[j];
	}

}



int main()
{
	int testList[] = {34, 5, 23, 12, 33, 98, 4, 13, 44, 37, 1, 86, 8};
	int size = 13;


	heapSort(testList, size);
	cout << "Lists should match " << endl;
	cout << "1, 4, 5, 8, 12, 13, 23, 33, 34, 37, 44, 86, 98" << endl;

	for(int i=0; i < size; i++)
	{
		cout << testList[i] << ", ";
	}
	cout << endl;


}

